package test;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author xushenbao
 * @desc 添加描述
 * @create 2020/11/10
 */
public class Leetcode1649 {
    static int mod = (int) 1e9 + 7;
    static int maxn = (int)1e5+2;

    static IntSumWithModNode abstractNode = new IntSumWithModNode();
    static IntSumWithModNode tmp = abstractNode.treeBuild(IntStream.rangeClosed(1,maxn).mapToObj(i->new Pair<>(i,0)).collect(Collectors.toList()));
    public int createSortedArray(int[] instructions) {
        tmp.reBuild(tmp,0);
        int ans = 0;
        for (int i = 0; i < instructions.length; i++) {
            int left = tmp.query(IntSumWithModNode.Queries.SUM, 0, instructions[i] - 1);
            int right = tmp.query(IntSumWithModNode.Queries.SUM, instructions[i] + 1, Integer.MAX_VALUE);
            ans += Math.min(left, right);
            ans %= mod;
            tmp.operate(IntSumWithModNode.Operate.ADD, 1, instructions[i], instructions[i]);
        }
        return ans;
    }


    static abstract class AbstractNode<V> {

        //region private
        public List<Pair<Integer,V>> originIndexValueList;
        //endregion

        //region protect
        protected int l;
        protected int r;
        public V value;
        protected AbstractNode<V> lson;
        protected AbstractNode<V> rson;

        //region 构造相关
        protected abstract AbstractNode<V> supplier();
        // 子节点完成构造或者更新过，父节点的更新操作,此时父节点的左右儿子已经赋值过
        protected abstract AbstractNode<V> updateNotLeaf();
        protected abstract <T extends AbstractNode> T self();
        // 提供一个非叶子节点，
        protected AbstractNode<V> supplierNotLeaf(int l,int r) {
            AbstractNode<V> supplier = supplier();
            supplier.l=l;
            supplier.r=r;
            return supplier;
        }
        protected AbstractNode<V> supplierLeaf(int pos,V v) {
            AbstractNode<V> supplier = supplier();
            supplier.l = pos;
            supplier.r = pos+1;
            supplier.value = v;
            return supplier;
        }
        //endregion

        private <N extends AbstractNode,I,O> O _visit(N now, Visitable<N,I,O> visitor, I input, int left, int right) {
            // 完全在区间内
            if (now.l >= left && now.r <= right) {
                return visitor.inRange(now,input);
            }
            // 不在区间内，提供一个可合并的空值
            if(now.l>=right||left>=now.r) {
                return visitor.notInRange(now,input);
            }

            return visitor.merge(now,
                    _visit((N) now.lson, visitor,input,left,right),
                    _visit((N) now.rson, visitor,input,left,right));
        }

        protected <N extends AbstractNode> N build(int l,int r) {
            if(r-l==1) {
                return (N) supplierLeaf(l,originIndexValueList.get(l).getValue());
            } else {
                int mid = (l+r)>>1;
                AbstractNode<V> vAbstractNode = supplierNotLeaf(l, r);
                vAbstractNode.lson = build(l,mid);
                vAbstractNode.rson = build(mid,r);
                return (N) vAbstractNode.updateNotLeaf();
            }
        }

        protected <T> void reBuild(AbstractNode<T> node,T t) {
            if(node.lson==null) {
                node.value = t;
            } else {
                reBuild(node.lson,t);
                reBuild(node.rson,t);
                node.updateNotLeaf();
            }
        }

        protected interface Visitable<N extends AbstractNode,I,O> {
            O inRange(N node,I input);
            O notInRange(N node,I input);
            O merge(N node,O leftOutput,O rightOutput);
        }
        //endregion


        //region static
        static <T> int lower_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
            while (left < right) {
                int mid = (left + right) >> 1;
                if (comparator.compare(indexToObject.apply(mid), aim) < 0) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }

        static <T> int upper_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
            while (left < right) {
                int mid = (left + right) >> 1;
                if (comparator.compare(indexToObject.apply(mid), aim) <= 0) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }
        static <A,B> List<Pair<A,B>> zip(List<A> aList,List<B> bList ) {
            if(aList.size()!=bList.size()) {
                throw new RuntimeException(String.format("两个列表的大小必须相等,aList size:%s,bList size:%s", aList,bList));
            }
            return IntStream.range(0,aList.size()).mapToObj(i->new Pair<>(aList.get(i),bList.get(i))).collect(Collectors.toList());
        }
        //endregion

        //region public
        public <N extends AbstractNode> N treeBuild(List<Integer> indexList,List<V> valueList){
            return treeBuild(zip(indexList,valueList));
        }
        public <N extends AbstractNode> N treeBuild(List<Pair<Integer, V>> indexValue){
            // 1. 将传入的数据按索引排序

            originIndexValueList = indexValue.stream().sorted(Comparator.comparing(Pair::getKey)).collect(Collectors.toList());
            // 2. 构建树
            AbstractNode build = build(0, indexValue.size());
            build.originIndexValueList = originIndexValueList;
            return (N) build;
        }
        public <N extends AbstractNode,I,O> O visit(Visitable<N,I,O> visitor, I input, int left, int right) {
            int l = lower_search(0,originIndexValueList.size(),left,i->originIndexValueList.get(i).getKey(),Integer::compare);
            int r = upper_search(0,originIndexValueList.size(),right,i->originIndexValueList.get(i).getKey(),Integer::compare);
            if(l>=r) {
//            return visitor.notInRange(self(),input);
                return visitor.notInRange(self(),input);
            }
            return _visit(self(), visitor,input,l,r);
        }

        public <O> O query(Visitable<? extends AbstractNode,Void,O> visitor, int left, int right) {
            return visit(visitor,null,left,right);
        }

        public <I> void operate(Visitable<? extends AbstractNode,I,Void> visitor, I input, int left, int right) {
            visit(visitor,input,left,right);
        }

        //endregion
    }



    static class IntSumWithModNode extends AbstractNode<Integer> {

        static int mod = (int) (1e9 + 7);

        public IntSumWithModNode() {
            super();
            value = 0;
        }

        @Override
        protected AbstractNode<Integer> supplier() {
            return new IntSumWithModNode();
        }

        @Override
        protected AbstractNode<Integer> updateNotLeaf() {
            this.value = (this.lson.value + this.rson.value) % mod;
            return this;
        }

        @Override
        protected <T extends AbstractNode> T self() {
            return (T) this;
        }

        public enum Operate implements Visitable<IntSumWithModNode, Integer, Void> {
            ADD {
                @Override
                public Void inRange(IntSumWithModNode node, Integer input) {
                    node.value = (node.value + input) % mod;
                    return null;
                }

                @Override
                public Void notInRange(IntSumWithModNode node, Integer input) {
                    return null;
                }

                @Override
                public Void merge(IntSumWithModNode node, Void leftOutput, Void rightOutput) {
                    node.updateNotLeaf();
                    return null;
                }
            },
            CHANGE {
                @Override
                public Void inRange(IntSumWithModNode node, Integer input) {
                    node.value = input % mod;
                    return null;
                }

                @Override
                public Void notInRange(IntSumWithModNode node, Integer input) {
                    return null;
                }

                @Override
                public Void merge(IntSumWithModNode node, Void leftOutput, Void rightOutput) {
                    node.updateNotLeaf();
                    return null;
                }
            }
        }

        public enum Queries implements Visitable<IntSumWithModNode, Void, Integer> {
            SUM {
                @Override
                public Integer inRange(IntSumWithModNode node, Void input) {
                    return node.value;
                }

                @Override
                public Integer notInRange(IntSumWithModNode node, Void input) {
                    return 0;
                }

                @Override
                public Integer merge(IntSumWithModNode node, Integer leftOutput, Integer rightOutput) {
                    return (leftOutput + rightOutput) % mod;
                }
            }
        }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        new Leetcode1649().createSortedArray(IntStream.of().toArray());
        long end = System.currentTimeMillis();
        System.out.println("cost:"+(end-start));
    }
}
